package bit;

/**
 * 题目： 不用加减求两个数的和
 *  由于不能使用加减，那么只能通过位运算来操作了
 *  y:
 * @Author Gavin
 * @date 2021.12.07 22:34
 */
public class bit_1 {

    /**
     *解题思路：由于不能使用加减符号，所以只能考虑使用位运算来处理
     * 所以这就要求我们对位运算比较熟悉了
     *      比如：  8  +  9
     *      二进制位：      1 0 0 0
     *                    1 0 0 1
     *     二进制相加：    1 0 0 0 1      这是二进制相加得到的结果，也是最终我们要的答案 17
     *
     *     所以我们需要寻找上面的规律： 不考虑进位的情况相当于就是两个数的异或运算
     *              与或运算：   1 0 0 0
     *                         1 0 0 1
     *                  结果1： 0 0 0 1      相同为0，不相同为1
     *
     *    最关键的就是进了位的二进制怎么表示： 这里就是用两个数做与运算，然后向左移动一位
     *              与运算:     1 0 0 0
     *                         1 0 0 1
     *                结果2：   1 0 0 0
     *     向左移动一位结果3： 1 0 0 0 0       这里就是原来的两个数进位产生的进制位，可以发现结果3和结果1相加刚好师17
     *
     *     然后我们就可以递归对结果3和结果1进行操作，最后让结果3变为0了之后，结果1就是最后的答案
     */



    //第一种，采用递归的方式
    public static int solution(int a,int b){
        return b==0?a:solution(a^b,(a&b)<<1);
    }

    //第二种方式，迭代的方式，思路都是上面的思路，只是按照迭代的方式实现
    public static int solution2(int a,int b){
        while (b!=0){
            int sum=a^b;
            int carry=(a&b)<<1;
            a=sum;
            b=carry;
        }
        return a;
    }


}
